翻訳と辞書 Words near each other ・ Post pounder ・ Post Present Medium ・ Post Primary Teachers' Association ・ Post processor ・ Post Properties ・ Post Punk Kitchen ・ Post Records ・ Post Regiment ・ Post Regiment (album) ・ Post Register ・ Post riders ・ Post Ridge ・ Post Break-Up Sex ・ Post bronchodilator test ・ Post Brothers Apartments ・ Post canonical system ・ Post Captain (novel) ・ Post Carbon Institute ・ POST card ・ Post church ・ Post City Magazines ・ Post conviction ・ Post Corner, New Jersey ・ Post correspondence problem ・ Post Danmark ・ Post Darreh ・ Post disputation argument ・ Post Ekspres Prima ・ Post Electric Blues ・ Post Falls Community United Presbyterian Church Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Post canonical system ： ウィキペディア英語版 Post canonical system A Post canonical system, as created by Emil Post, is a string-manipulation system that starts with finitely-many strings and repeatedly transforms them by applying a finite set j of specified rules of a certain form, thus generating a formal language. Today they are mainly of historical relevance because every Post canonical system can be reduced to a string rewriting system (semi-Thue system), which is a simpler formulation. Both formalisms are Turing complete. == Definition == A Post canonical system is a triplet (A,I,R), where * A is a finite alphabet, and finite (possibly empty) strings on A are called ''words''. * I is a finite set of ''initial words''. * R is a finite set of string-transforming rules (called ''production rules''), each rule being of the following form: :$$ \overset & $_ & g_ & $_ & g_ & \dots & $_ & g_ \\ g_ & $_ & g_ & $_ & g_ & \dots & $_ & g_ \\ \vdots & \vdots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ g_ & $_ & g_ & $_ & g_ & \dots & $_ & g_ \\ \end } } } where each and is a specified fixed word, and each ''$'' and ''$' '' is a variable standing for an arbitrary word. The strings before and after the arrow in a production rule are called the rule's ''antecedents'' and ''consequent'', respectively. It is required that each ''$' '' in the consequent be one of the ''$''s in the antecedents of that rule, and that each antecedent and consequent contain at least one variable. In many contexts, each production rule has only one antecedent, thus taking the simpler form : $g\_0\; \backslash \; \$\_1\; \backslash \; g\_1\; \backslash \; \$\_2\; \backslash \; g\_2\; \backslash \; \backslash dots\; \backslash \; \$\_m\; \backslash \; g\_m\; \backslash \; \backslash rightarrow\; \backslash \; h\_0\; \backslash \; \$\text{'}\_1\; \backslash \; h\_1\; \backslash \; \$\text{'}\_2\; \backslash \; h\_2\; \backslash \; \backslash dots\; \backslash \; \$\text{'}\_n\; \backslash \; h\_n$ The formal language generated by a Post canonical system is the set whose elements are the initial words together with all words obtainable from them by repeated application of the production rules. Such sets are recursively enumerable languages and every recursively enumerable language is the restriction of some such set to a sub-alphabet of A. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Post canonical system」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.